package com.heima.algorithm.sort;

/**
 * <strong>自底至上归并排序</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/30 19:28
 */
public class MergeSortBottomUp {
    //（1）基于比较的排序算法
    //（2）最好情况：O(NlogN)，最坏情况：O(NlogN)，平均情况：O(NlogN)，空间复杂度：O(N)，稳定：是，思想：分而治之
    //（3）注意事项：需要额外O(N)的空间
    //（4）时间复杂度需要主定理来算

    /**
     * 自底至上归并排序
     * @param arr 待排序的数组
     */
    public static void mergeSort(int[] arr) {
        // 记录待排序的数组长度
        int length = arr.length;
        // 用来存放合并后的结果的临时数组
        int[] result = new int[length];
        // width记录的已合并已排序的分组范围，最开始就是1，每次乘以二，也就是相邻分组合并，width要小于length，表示还有未排序的元素
        for (int width = 1; width < length; width *= 2){
            // begin表示待合并的相邻分组的起始位置，合并相邻的两个分组，最后可能剩一个分组，让他自己和自己合并
            for (int begin = 0; begin < length; begin += width * 2){
                // end应该是相邻的第二个分组的最后一个元素，有可能没有第二个分组或者第二个分组元素个数小于width
                int end = Math.min(begin + 2 * width - 1, length - 1);
                // 当前分组也有可能小于width
                int median = Math.min(begin + width - 1, length - 1);
                merge(arr, begin, median, end, result);
            }
            System.arraycopy(result, 0, arr, 0, length);
        }
    }

    /**
     * 拷贝左右两个有序数组，合并成一个新的有序数组
     * @param arr 数组
     * @param begin 左数组的第一个元素
     * @param median 左数组的最后一个元素，也是右数组的第一个元素的前一个元素
     * @param end  右数组的最后一个元素
     * @param result 存放合并后的结果的数组
     */
    private static void merge(int[] arr, int begin, int median, int end, int[] result) {
        // 指针p1指向左边数组的首元素
        int p1 = begin;
        // 指针p2指向右边数组的首元素
        int p2 = median + 1;
        // 指针start指向合并后的数组的起始位置
        int start = begin;
        // 只要p1或者p2有一个没有移动到边界，就继续循环
        while (p1 <= median || p2 <= end){
            // 两者都还有元素
            if (p1 <= median && p2 <= end){
                // 比较两个元素，将较小的元素放入合并后的数组中
                if (arr[p1] <= arr[p2]){
                    result[start++] = arr[p1++];
                }else {
                    result[start++] = arr[p2++];
                }
            }
            // 左边还有元素，但是右边已经处理完了
            else if (p1 <= median) {
                System.arraycopy(arr, p1, result, start, median - p1 + 1);
                return;
            }
            // 右边还有元素，但是左边已经处理完了
            else {
                System.arraycopy(arr, p2, result, start, end - p2 + 1);
                return;
            }
        }
    }
}
